package leetcode_day._2023._11;

import java.util.HashSet;
import java.util.Set;

/**
 * 421. 数组中两个数的最大异或值
 * 算法: 位运算
 * 从最高位开始判断, 每一位是否可以取到 1
 *
 * @author yezh
 * @date 2023/11/19 14:06
 */
public class _04 {

    public int findMaximumXOR(int[] nums) {
        int max = 0;
        for (int num : nums) max = Math.max(num, max);
        // 无符号整数的最高非 0 位前面的 0 的个数
        int highBit = 31 - Integer.numberOfLeadingZeros(max);
        int ans = 0, mask = 0;
        Set<Integer> seen = new HashSet<>();
        for (int i = highBit, newAnswer; i >= 0; i--) {
            seen.clear();
            mask |= (1 << i);
            // 能否得到这个数
            newAnswer = ans | (1 << i);
            for (int num : nums) {
                num &= mask;
                // a ^ b = newAnswer, a = a ^ b ^ b = newAnswer ^ b
                // 可以得到这个数
                if (seen.contains(newAnswer ^ num)) {
                    ans = newAnswer;
                    break;
                }
                seen.add(num);
            }
        }
        return ans;
    }

}
